package com.example.demo.leetcode;

import java.util.Arrays;

/**
 * 解数独
 */
public class Leetcode37 {
    public static void main(String[] args) {
        char[][] board = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        solveSudoku(board);
        printBoard(board);
    }

    public static void solveSudoku(char[][] board) {
        // 记录行冲突状态
        boolean[][] ca = new boolean[9][9];
        // 记录列冲突状态
        boolean[][] cb = new boolean[9][9];
        // 小九宫格冲突状态
        boolean[][] cc = new boolean[9][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char s = board[i][j];
                if (s != '.') {
                    int num = s - '1';
                    ca[i][num] = true;
                    cb[j][num] = true;
                    cc[i / 3 * 3 + j / 3][num] = true;
                }
            }
        }
        dfs(0, 0, board, ca, cb, cc);
    }

    static boolean dfs(int i, int j, char[][] board, boolean[][] ca, boolean[][] cb, boolean[][] cc) {
        // 寻找下一个需要填充的空格
        while (board[i][j] != '.') {
            if (++j >= 9) {
                j = 0;
                if (++i >= 9) {
                    return true;
                }
            }
        }

        for (int k = 1; k <= 9; k++) {
            if (ca[i][k - 1] || cb[j][k - 1] || cc[i / 3 * 3 + j / 3][k - 1]) {
                continue;
            }
            board[i][j] = (char) (k + '0');
            ca[i][k - 1] = true;
            cb[j][k - 1] = true;
            cc[i / 3 * 3 + j / 3][k - 1] = true;
            if (dfs(i, j, board, ca, cb, cc)) {
                return true;
            }
            board[i][j] = '.';
            ca[i][k - 1] = false;
            cb[j][k - 1] = false;
            cc[i / 3 * 3 + j / 3][k - 1] = false;
        }
        return false;
    }

    static void printBoard(char[][] board) {
        for (int i = 0; i < 9; i++) {
            System.out.println(Arrays.toString(board[i]));
        }
    }
}
